package com.algrithom.dfs;

import java.util.HashMap;
import java.util.Map;

/**
 * 887. 鸡蛋掉落
 * 
 * @author think
 */
public class Solution9 {
    
    Map<Integer,Integer> memo = new HashMap<Integer,Integer>();
    
    public static void main(String[] args){
        Solution9 solution9 = new Solution9();
        System.out.println(solution9.dfs(1,2));
    }
    
    public int dfs(int k,int n){
        if (!memo.containsKey(n * 100 + k)) {
            int ans;
            if (n == 0) {
                ans = 0;
            } else if (k == 1) {
                ans = n;
            } else {
                int lo = 1;
                int hi = n;
                while (lo + 1 < hi) {
                    int mid = (lo + hi) / 2;
                    int t1 = dfs(k - 1,mid - 1);
                    int t2 = dfs(k,n - mid);
                    
                    if (t1 < t2) {
                        lo = mid;
                    } else if (t1 > t2) {
                        hi = mid;
                    } else {
                        lo = hi = mid;
                    }
                }
                
                ans = 1 + Math.min(Math.max(dfs(k - 1,lo - 1),dfs(k,n - lo)),Math.max(dfs(k - 1,hi - 1),dfs(k,n - hi)));
            }
            memo.put(n * 100 + k,ans);
        }
        
        return memo.get(n * 100 + k);
    }
}